public class code01s {
//    力扣 150 二叉树的层平均值
public List<Double> averageOfLevels(TreeNode root) {
    // 解法二：通过深度优先搜索对数据进行记录并计算
    // 深度优先搜索是没有广度优先搜索好理解的。。
    // 这里就需要两个数组来维护相关值
    // 一个数组记录当前二叉树每一层的元素个数
    // 一个数组记录当前二叉树每一层的元素之和

    // 这里创建的都是数组类型的顺序表，就是为了对应下标操作数据
    List<Integer> count = new ArrayList<>();
    List<Double> sum = new ArrayList<>();

    // 实现深度优先搜索算法，将树中的值记录计算下来
    dfs(root, 0, count, sum);

    // 在来定义一个顺序表，用来记录计算得到的平均值
    List<Double> avg = new ArrayList<>();

    // 在完成下面的递归之后，这里将两个数组中的值按照要求进行一下计算
    int size = sum.size();
    for(int i = 0; i < size; i++) {
        avg.add(sum.get(i) / count.get(i));
    }

    return avg;
}


    // 这里需要传入的参数有，根节点、数组对应下标、个数记录表、总和记录表
    private void dfs(TreeNode node, int index, List<Integer> c, List<Double> s) {
        // 首先定义返回条件
        if(node == null) {
            return;
        }

        // 设计递归计算条件
        // 如果这里的下标值比 s 的 size() 小，此时就说明在这个下标下的元素时有同一行的需要进行加和计算
        if(index < s.size()) {
            // 此时就需要更新当前下标下 s 记录的当前行的值
            s.set(index, s.get(index) + node.val);
            // 同样跟新当前行的元素个数
            c.set(index, c.get(index) + 1);
        } else {
            // index 的值大于某一行的值时，此时就说明这是新的一行，就在两个数组中新建一个元素信息
            // 这里是需要将当前 node 节点中的值刷新为 double 类型的值
            s.add(1.0 * node.val);
            c.add(1);
        }
        // 分别进行递归计算左右子树上的节点
        dfs(node.left, index+1, c, s);
        dfs(node.right, index+1, c, s);
    }
}
